import java.util.*;

//通过穷举的方式建立一个二叉树
//孩子表示法
public class BinaryTree {
    class TreeNode{
        private char val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }

        public char getVal() {
            return val;
        }

        public void setVal(char val) {
            this.val = val;
        }
    }
    //根结点 root一直指向，防止空间被收回
    private TreeNode root;

    public TreeNode getRoot() {
        return root;
    }

    public TreeNode creatBinaryTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        root=A;
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        E.right=H;
        C.left=F;
        C.right=G;
        return root;
    }
    // 前序遍历
    void preOrder(TreeNode root){
        if(root==null)return;//当前的结点为null时返回
        System.out.print(root.val);//根
        //调用左子树
        preOrder(root.left);
        //调用右子树
        preOrder(root.right);
    };
    // 中序遍历
    void inOrder(TreeNode root){
        //当前的结点为null时返回
        if(root==null)return;
        //调用左子树
        inOrder(root.left);
        //根
        System.out.print(root.val);
        //调用右子树
        inOrder(root.right);
    };
    // 后序遍历
   public void  postOrde(TreeNode root){
        //当前的结点为null时返回
        if(root==null)return;
        //调用左子树
        postOrde(root.left);
        //调用右子树
        postOrde(root.right);
        //根
        System.out.print(root.val);
    };
   //给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
    public List<Character> preorderTraversal(TreeNode root) {
        List<Character>ret=new LinkedList<>();
        if(root==null)return ret;
        //根
        ret.add(root.val);
        //左子树
        List<Character> leftList=preorderTraversal(root.left);
        ret.addAll(leftList);
        //右子树
        List<Character> rightList=preorderTraversal(root.right);
        ret.addAll(rightList);
        return ret;
    }
    //子问题思路
    // 获取树中节点的个数
    /*public int size(TreeNode root){
        if(root==null)return 0;
        //只要走到这里，说明是有结点的，所以默认是1
        int count=1;
        int countL=size(root.left);
        count+=countL;
        int countR=size(root.right);
        count+=countR;
        return count;
    };*/
    public int size(TreeNode root){
        if(root==null)return 0;
        return size(root.left)+size(root.right)+1;
    }

    //遍历思路
    // 获取树中节点的个数
    private int count=0;
    public int size1(TreeNode root){
        if(root==null)return 0;
        count++;
        size1(root.left);
        size1(root.right);
        return count;
    };

    // 遍历思路
    // 获取叶子节点的个数
    private int count1=0;
    public int getLeafNodeCount(TreeNode root){
        if(root==null)return 0;
        if(root.right==null&&root.left==null){
            count1++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return count1;
    };

    // 子问题思路-求叶子结点个数
    public int getLeafNodeCount2(TreeNode root) {
        if (root == null) return 0;
        if (root.right == null && root.left == null) {
            return 1;
        }
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }



    //子问题
    // 获取第K层节点的个数
    public int getKLevelNodeCount(TreeNode root,int k){
       if(root==null)return 0;
       //走到这里说明root不为null
       if(k==1)return 1;
       return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    };


    // 获取二叉树的高度
    public  int getHeight(TreeNode root){
       if(root==null)return 0;
       return getHeight(root.left)>getHeight(root.right)?
               getHeight(root.left)+1:getHeight(root.right)+1;
    };
    // 检测值为value的元素是否存在
    public  TreeNode find(TreeNode root, char val){
        if(root==null)return null;
        if(root.val==val){
            return root;
        }
        TreeNode curleft=find(root.left,val);
        if(curleft!=null){
            return curleft;
        }
        TreeNode curright=find(root.right,val);
        if(curright!=null){
            return curright;
        }
        return null;
    };

    private List<Character> fun(TreeNode tmp){
        List<Character> ret=new ArrayList<>();
        if(tmp==null){
            ret.add(null);
            return ret;
        }
        ret.add(tmp.val);
        List<Character> retLeft=fun(tmp.left);
        ret.addAll(retLeft);
        List<Character> retright=fun(tmp.right);
        ret.addAll(retright);
        return ret;
    }
    public boolean isSameTree1(TreeNode p, TreeNode q) {
        List<Character> list1=fun(p);
        List<Character> list2=fun(q);
        //元素个数不同直接false
        if(list1.size()!=list2.size())return false;
        for (int i = 0; i < list1.size(); i++) {
            if(!(list1.get(i).equals(list2.get(i)))){
                return false;
            }
        }
        return true;
    }
    public boolean isSameTree2(TreeNode p, TreeNode q) {
      if(p==null&&q==null){
          return true;
      }
      //其中一个为null就返回false
      if(p==null&&q!=null||q==null&&p!=null){
          return false;
      }
      if(p.val!=q.val){
          return false;
      }
      return isSameTree2(p.left,q.left)&&isSameTree2(p.right,q.right);
    }
    //另一棵树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //递归终止条件
        if(root==null)return false;
        if(isSameTree2(root,subRoot)){
            return true;
        }
       return isSubtree(root.left, subRoot)||isSubtree(root.right, subRoot);
    }
    //二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if(root==null)return 0;
        int left=maxDepth(root.left);
        int right=maxDepth(root.right);
        return left>right?left+1:right+1;
    }

    //计算一个节点的高度
    public int fun1(TreeNode root){
        if(root==null)return 0;
        int left=fun1(root.left);
        int right=fun1(root.right);
        return left>right?left+1:right+1;
    }
    //判断平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if(root==null)return true;
        //计算左子树右子树的高度差
        int left=fun1(root.left);
        int right=fun1(root.right);
        if(Math.abs(left-right)>1){
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);
    }

    //O（N）
    //计算一个节点的高度
    public int fun3(TreeNode root){
        if(root==null)return 0;
        int left=fun3(root.left);
        int right=fun3(root.right);
        if(left>=0&&right>=0&&Math.abs(left-right)<=1){
            return Math.max(left,right)+1;//把最大值加1返回回去
        }else{
            return -1;
        }
    }
    //判断平衡二叉树
    public boolean isBalanced1(TreeNode root) {
        if(root==null)return true;
        return fun3(root)>=0;
    }

    //判断左树的左和右树的右  左树的右和右树的左 是否相同即可
    private boolean fun4(TreeNode p,TreeNode q){
        if(p==null&&q==null)return true;
        if(p==null&&q!=null||p!=null&&q==null){
            return false;
        }
        if(p.val!=q.val){
            return false;
        }
        return fun4(p.left,q.right)&& fun4(p.right,q.left);
    }
    //判断对称二叉树
    public boolean isSymmetric(TreeNode root) {
        return fun4(root.left,root.right);
    }


    //层序遍历
    public void levelOrder(TreeNode root){
        if(root==null)return;
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.print(cur.val);
            if(cur.left!=null){
                queue.offer(root);
            }
            if(cur.right!=null){
                queue.offer(root);
            }
        }
    };
    //层序遍历每一层放入链表中
    public List<List<Character>> levelOrder1(TreeNode root) {
        List<List<Character>>ret=new ArrayList<>();
        if(root==null)return ret;
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            List<Character>tmp=new ArrayList<>();//存每一层元素
            int size=queue.size();//记录每一次循环过后队内元素（每一层的元素个数）
            while (size>0){//队内几个元素就出队几次,并且入队他的所有孩子
                TreeNode cur=queue.poll();//出队
                tmp.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(tmp);
        }
        return ret;
    }
    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if(root==null)return false;
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root);//根入队
        while (!queue.isEmpty()){
            //出队
            TreeNode cur=queue.poll();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()){
            TreeNode tmp=queue.peek();
            if(tmp!=null){
                return false;
            }else {
                queue.poll();
            }
        }
        return true;
    };
}
